package lcsRec;

/**
 * Classe statica per la ricerca ricorsiva della Long Common Subsequence
 * @author RaF
 *
 */
public class RecursiveLCS {

	/**
	 * Calcola la Long Common Subsequence in maniera ricorsiva su due stringhe.
	 * @param s1 prima stringa da confrontare
	 * @param s2 seconda stringa da confrontare
	 * @return LCS calcolata
	 */
	public static String findLCS(String s1, String s2){
		String result="";
		int s1Lenght=s1.length();
		int s2Lenght=s2.length();
		
		//caso base
		if(s1Lenght == 0 || s2Lenght == 0)
			return "";
		
		if(s1.charAt(s1Lenght-1) == s2.charAt(s2Lenght-1))
		{
			result=findLCS(s1.substring(0,s1Lenght-1), s2.substring(0,s2Lenght-1))+ s1.charAt(s1Lenght-1);
		}
		else
		{
			//caso X_i != Y_j
			String lcs1="",lcs2="";
			lcs1=findLCS(s1.substring(0,s1Lenght-1), s2);
			lcs2=findLCS(s1,s2.substring(0,s2Lenght-1));
			
			if(lcs1.length() > lcs2.length()){
				result=lcs1;
			}
			else
				result=lcs2;			
		}
		
		return result;
	}
}
